coins = [200, 100, 50, 20, 10, 5, 2, 1]

n = 0
def poss(money, yet_used):
	n = 0
	if yet_used >= len(coins)-1: return 1
	for i,val in enumerate(coins[yet_used:]):
		remained = money-val
		if remained==0: 
			n+=1
		elif remained>0:
			n+=poss(remained, i+yet_used)
	return n



def possibilities(amount, coins):
	if amount==0 or len(coins)==1:
		return amount==0 or amount%coins[0]==0
	branches = 0
	for i in range(1+amount//coins[0]):
		branches += possibilities(amount-i*coins[0], coins[1:])
	return branches

from time import time

s = time()
print(possibilities(200, coins))
print(time()-s)

s = time()
print(poss(200, 0))
print(time()-s)
